package LRU;

import java.util.HashMap;
import java.util.Map;

public class LRUCache
{
    private class Node{
         int key;
         int value;
         Node next;
         Node pre;
         public Node(int key, int value){
             this.key = key;
             this.value = value;
             next = null;
             pre = null;
         }
    }
    int capacity;
    Node dummy = new Node(-1,-1);
    Map<Integer,Node> map;
    public LRUCache(int capacity){
        this.capacity = capacity;
        dummy.next = dummy;
        dummy.pre = dummy;
        map = new HashMap<Integer,Node>(capacity);
    }
    public int get(int key){
       Node node = getNode(key);
       if(node == null) return -1;
       return node.value;
    }
    public void put(int key, int value){
        Node node = getNode(key);
        if(node !=null){
            node.value = value;
            return;
        }else{
            node = new Node(key,value);
            if(map.size()>=capacity){
                Node last = dummy.pre;
                remove(last);
                map.remove(last.key);
            }
            pushFront(node);
            map.put(key,node);
        }
    }
    public  Node getNode(int key){
        Node node = null;
        if(map.containsKey(key)){
             node = map.get(key);
            remove(node);
            pushFront(node);
        }
        return node;
    }
    public void remove(Node node){
        dummy.pre = node.pre;
        node.pre.next = node.next;
    }
    public void pushFront(Node node){
        node.pre = dummy;
        node.next = dummy.next;
        dummy.next.pre = node;
        dummy.next = node;
    }
}
